package com.jinxi.algorithm.list;

public class Linked {


    public static Node init() {
        Node node1 = new Node(1);
        Node node2 = new Node(8);
        Node node3 = new Node(3);
        Node node4 = new Node(6);
        Node node5 = new Node(5);
        Node node6 = new Node(4);
        Node node7 = new Node(7);
        Node node8 = new Node(2);
        Node node9 = new Node(9);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = node7;
        node7.next = node8;
        node8.next = node9;
        node9.next = null;

        return node1;
    }

    /**
     * 遍历
     * @param head
     */
    public static void traverse(Node head) {

        while (head != null) {
            System.out.print(head.val + "   ");
            head = head.next;
        }

    }

    /**
     * 获取中间元素   快慢指针
     * @param head
     * @return
     */
    public static Node getMid(Node head) {
        Node point = head;
        while (head != null && head.next != null) {
            point = point.next;
            head = head.next.next;
        }
        return point;
    }

    /**
     * 拆分列表   下标 奇数，偶数拆分
     * @param head
     * @return
     */
    public static Node[] split(Node head) {
        Node head1 = null;
        Node head2 = null;
        Node cul1 = null;
        Node cul2 = null;

        int count = 1;
        while (head != null) {

            if (count % 2 == 1) {
                if (cul1 != null) {
                    cul1.next = head;
                    cul1 = cul1.next;
                } else {
                    cul1 = head;
                    head1 = cul1;
                }
            } else {
                if (cul2 != null) {
                    cul2.next = head;
                    cul2 = cul2.next;
                } else {
                    cul2 = head;
                    head2 = cul2;
                }
            }

            head = head.next;
            count++;
        }
        cul1.next = null;
        cul2.next = null;

        Node[] nodes = new Node[]{head1, head2};

        return nodes;
    }


    /**
     * 反转列表
     * @param head
     * @return
     */
    public static Node revert(Node head) {

        Node pre = null;
        Node next = null;
        while (head != null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

    public static Node merge(Node head1, Node head2) {
        if (head1 == null && head2 == null) {
            return null;
        }
        if (head1 == null) {
            return head2;
        }
        if (head2 == null) {
            return head1;
        }
        Node head;
        if (head1.val < head2.val) {
            head = head1;
            head.next = merge(head1.next, head2);
        } else {
            head = head2;
            head.next = merge(head1, head2.next);
        }

        return head;
    }

    public static void main(String[] args) {
        Node head = init();
        traverse(head);
        System.out.println();
        System.out.println(getMid(head).val);

        Node[] nodes = split(head);
        Node head1 = nodes[0];
        Node head2 = nodes[1];
        traverse(head1);
        System.out.println();
        traverse(head2);
        System.out.println();

        Node rhead2 = revert(head2);
        traverse(rhead2);
        System.out.println();

        Node hd = merge(head1, rhead2);
        traverse(hd);
    }


    public static class Node {
        public int val;
        private Node next;


        public Node(int val) {
            this.val = val;
        }
    }

}
